package solution1.demo.demo4;



class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {

    //1.翻转二叉树(dfs)
    private void dfs(TreeNode root) {
        if(root == null) {
            return;
        }
        dfs(root.right);
        root.val += prev.val;
        prev = root;
        dfs(root.left);
    }

    private TreeNode prev = new TreeNode(0);
    public TreeNode convertBST(TreeNode root) {
        dfs(root);
        return root;
    }

    //2.对称二叉树(dfs)
    private boolean checkTree(TreeNode leftRoot, TreeNode rightRoot) {
        if(leftRoot == null && rightRoot == null) {
            return true;
        }
        if((leftRoot != null && rightRoot == null) ||
                (leftRoot == null && rightRoot != null)) {
            return false;
        }
        if(leftRoot.val != rightRoot.val) {
            return false;
        }
        return checkTree(leftRoot.left, rightRoot.right) &&
                checkTree(leftRoot.right, rightRoot.left);
    }

    public boolean isSymmetric(TreeNode root) {
        if(root == null) {
            return true;
        }
        return checkTree(root.left, root.right);
    }

    //3.二叉树的最小深度(dfs)
//    private void dfs(TreeNode root, int depth) {
//        if(root == null) {
//            return;
//        }
//        if(root.left == null && root.right == null) {
//            if(depth < min) {
//                min = depth;
//            }
//            return;
//        }
//        dfs(root.left, depth + 1);
//        dfs(root.right, depth + 1);
//    }
//
//    private int min = Integer.MAX_VALUE;
//    public int minDepth(TreeNode root) {
//        if(root == null) {
//            return 0;
//        }
//        dfs(root, 1);
//        return min;
//    }

    //4.二叉树的最小深度(另一种dfs)
    public int minDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        if(root.left == null && root.right != null) {
            return minDepth(root.right) + 1;
        }
        if(root.left != null && root.right == null) {
            return minDepth(root.left) + 1;
        }
        if(root.left == null && root.right == null) {
            return 1;
        }
        return Math.min(minDepth(root.left) + 1, minDepth(root.right) + 1);
    }

    //5.平衡二叉树(dfs)
    private int maxDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left) + 1, maxDepth(root.right) + 1);
    }

    public boolean isBalanced(TreeNode root) {
        if(root == null) {
            return true;
        }
        //分别求左右子树的深度
        if(Math.abs(maxDepth(root.left) - maxDepth(root.right)) > 1) {
            return false;
        }
        return isBalanced(root.left) &&
                isBalanced(root.right);
    }

    //6.左叶子之和(dfs)
    public int sumOfLeftLeaves(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int left = 0;
        int right = 0;
        if(root.left == null && root.right == null) {
            return 0;
        }
        if(root.left != null && root.left.right == null && root.left.left == null) {
            left += root.left.val;
        }
        left += sumOfLeftLeaves(root.left);
        right += sumOfLeftLeaves(root.right);
        return left + right;
    }

    //7.找树左下角的值(dfs)
    private void dfs(TreeNode root, int depth) {
        if(root == null) {
            return;
        }
        if(depth > beforeDepth) {
            target = root.val;
            beforeDepth++;
        }
        dfs(root.left, depth + 1);
        dfs(root.right, depth + 1);
    }

    private int target;
    private int beforeDepth;
    public int findBottomLeftValue(TreeNode root) {
        target = root.val;
        dfs(root, 0);
        return target;
    }

    //8.从中序与后序遍历序列构造二叉树(dfs)
    private TreeNode createTree(int[] inorder, int[] postorder, int left, int right) {
        if(left > right) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[postorderIndex]);
        int inorderRootIndex =
                fundIndexFromInorder(inorder, postorder[postorderIndex], left, right);
        postorderIndex--;
        root.right = createTree(inorder, postorder, inorderRootIndex + 1, right);
        root.left = createTree(inorder, postorder, left, inorderRootIndex - 1);
        return root;
    }

    private int fundIndexFromInorder(int[] inorder, int key, int left, int right) {
        for(int i = left; i <= right; i++) {
            if(inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }

    private int postorderIndex;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postorderIndex = postorder.length - 1;
        return createTree(inorder, postorder, 0, inorder.length - 1);
    }

    //9.二叉树的最近公共祖先(dfs)
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return root;
        }
        if (root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left == null && right == null) {
            return null;
        } else if (left != null && right == null) {
            return left;
        } else if (right != null && left == null) {
            return right;
        } else {
            return root;
        }
    }

    //10.修剪二叉搜索树(dfs)
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if(root == null) {
            return root;
        }
        if(root.val < low) {
            TreeNode node = trimBST(root.right, low, high);
            return node;
        }
        if(root.val > high) {
            TreeNode node = trimBST(root.left, low, high);
            return node;
        }
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;
    }
}
